import lombok.val;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import javax.management.MBeanNotificationInfo;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ZhengDp
 * @Date 2023/4/11 16:53
 */
public class 分治_回溯 {

    /*
     * #problem 50 Pow(x,n)
     * */
    // 1. 暴力解法 O(n) 会超时
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        double res = 1.0;
        for (int i = 1; i <= n; ++i) {
            res *= x;
        }
        return res;
    }

    // 2. 分治
    public double myPow1(double x, int n) {
        long N = n;
        if (n < 0) {
            x = 1 / x;
            return fastPow(x, -N);
        } else {
            return fastPow(x, N);
        }

    }

    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        double subResult = fastPow(x, n / 2);
        // odd
        if (n % 2 == 1) {
            return subResult * subResult * x;
        } else {
            return subResult * subResult;
        }
    }

    /*
     * #problem 78 子集
     * */
    // 1. 回溯 --> 找到所有可能性,且要保证非重
    // 每一步都有两种选择 --> 填充到数组 / 不填充到数组
    // 不回头选择 --> 保证生成的最终结果不会重复
    private List<Integer> temp = new LinkedList();
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int cur) {
        if (cur == nums.length) {
            res.add(new ArrayList(temp));
            return;
        }
        temp.add(nums[cur]);
        dfs(nums, cur + 1);
        temp.remove(temp.size() - 1);
        dfs(nums, cur + 1);
    }

    // 动态规划
    //  包含当前数的子集组合=上一个数的获得的每一个子集组合+当前数。所有子集=遍历的每一个数的获得的子集组合的合集
    public List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        // 加入空集
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            int size = res.size();
            for (int j = 0; j < size; j++) {
                List<Integer> newList = new ArrayList<>(res.get(j));
                newList.add(nums[i]);
                res.add(newList);
            }
        }
        return res;
    }

    /*
     * #problem 169 多数元素
     * */
    // 1. Map计数
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        int n = nums.length / 2;
        for (int i = 0; i < nums.length; ++i) {
            int count = map.getOrDefault(nums[i], 0);
            count++;
            if (count > n) {
                return nums[i];
            }
            map.put(nums[i], count);
        }
        return -1;
    }

    // 2. 排序
    // 因为众数的个数大于 n/2个，所以其所占的格子一定大于 n/2个
    // 那么排序之后 下标为 n/2的数一定为众数
    public int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    //3. Boyer-Moore
    public int majorityElement2(int[] nums) {
        int count = 0;
        Integer canadidate = null;
        for (int num : nums) {
            if (count == 0) {
                canadidate = num;
            }
            count += num == canadidate ? 1 : -1;
        }
        return canadidate;
    }

    // 4. 分治
    // 如果a为nums的众数，那么将nums分为left 和 right , a 至少是left或者right其中一个的众数
    public int majorityElement3(int[] nums) {
        return majorityElementFunction(nums, 0, nums.length - 1);
    }

    private int majorityElementFunction(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (right - left) / 2 + left;
        int leftM = majorityElementFunction(nums, left, mid);
        int rightM = majorityElementFunction(nums, mid + 1, right);
        if (leftM == rightM) {
            return leftM;
        }
        int leftCount = countMajority(nums, left, mid, leftM);
        int rightCount = countMajority(nums, mid + 1, right, rightM);
        return leftCount > rightCount ? leftM : rightM;
    }

    private int countMajority(int[] nums, int left, int right, int num) {
        int count = 0;
        while (left <= right) {
            if (nums[left] == num) {
                count++;
            }
            left++;
        }
        return count;
    }

    /*
     * #problem 17 电话号码的字母组合
     * */
    // 1.回溯
    private Map<Character, char[]> map = new HashMap<>();

    {
        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d', 'e', 'f'});
        map.put('4', new char[]{'g', 'h', 'i'});
        map.put('5', new char[]{'j', 'k', 'l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p', 'q', 'r', 's'});
        map.put('8', new char[]{'t', 'u', 'v'});
        map.put('9', new char[]{'w', 'x', 'y', 'z'});
    }

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0) {
            return res;
        }

        generateLetter(digits, 0, new char[digits.length()], res);
        return res;
    }

    private void generateLetter(String digits, int pos, char[] str, List<String> res) {
        if (pos == digits.length()) {
            res.add(new String(str));
            return;
        }
        char c = digits.charAt(pos);
        char[] list = map.get(c);
        for (char s : list) {
            str[pos] = s;
            generateLetter(digits, pos + 1, str, res);
        }
    }

    // 2. 状态枚举
    // 先求总可能性有多少种，再用求余拿到每一种
    // （可以当做是状态压缩吧，000代表都是第0位，001代表前两个第0位，第三个第1位，002。。。以此类推）
    public List<String> letterCombinations1(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        int len = 1;
        String[] strs = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int i = 0; i < digits.length(); i++) {
            int c = digits.charAt(i) - '0';
            len *= strs[c].length();
        }
        // 状态枚举
        for (int i = 0; i < len; i++) {
            int last = i;
            StringBuilder sb = new StringBuilder();
            for (int j = digits.length() - 1; j >= 0; j--) {
                int c = digits.charAt(j) - '0';
                int pos = last % strs[c].length();
                sb.append(strs[c].charAt(pos));
                last = last / strs[c].length();
            }
            res.add(sb.reverse().toString());
        }
        return res;
    }

    /*
     * #problem 51 N皇后
     * */
    @Test
    void test() {
        System.out.println(solveNQueens(4));
    }
    // 1. 回溯-没有咋剪枝 ==> 需要最后判断结果是否正确
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<String> temp = new LinkedList<>();
        List<String> situation = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        for(int i =0;i<n;i++) {
            str.append(".");
        }
        for(int i =0;i<n;i++) {
            str.replace(i,i+1,"Q");
            situation.add(str.toString());
            str.replace(i,i+1,".");
        }
        nQueens(n,res,temp,0,situation,new boolean[n]);
        return res;
    }

    private void nQueens(int n, List<List<String>> res,
                         List<String> temp, int column,List<String> situation,boolean[] used) {
        if (column == n) {
            if(valid(temp)){
                res.add(new ArrayList<>(temp));
            }
            return ;
        }
        // 在当前行要将皇后放置到哪一列
        for(int i =0;i<n;i++) {
            if(used[i]) {
                continue;
            }
            temp.add(situation.get(i));
            used[i] = true;
            nQueens(n,res,temp,column+1,situation,used);
            temp.remove(temp.size()-1);
            used[i] = false;
        }
    }

    // 判断N皇后是否成立
    private boolean valid(List<String> temp) {
        Set<Integer> lines = new HashSet<>();
        Set<String> coordinates = new HashSet<>();
        for(int i = 0; i < temp.size(); i++) {
            String t = temp.get(i);
            for(int j = 0;j<t.length();j++) {
                if(t.charAt(j) == 'Q') {
                    String coordinate = i+"," +j;
                    if(lines.contains(j) || coordinates.contains(coordinate)) {
                        return false;
                    }
                    lines.add(j);
                    addCoordinate(coordinates,i,j,temp.size());
                }
            }
        }
        return true;
    }

    private void addCoordinate(Set<String> coordinates,int i,int j ,int n) {
        int line = i;
        int column = j;
        while(line< n && column < n) {
            String val = line + "," + column;
            coordinates.add(val);
            line++;
            column++;
        }
        line = i;
        column = j;
        while(line >= 0 && column>=0) {
            String val = line + "," + column;
            coordinates.add(val);
            line--;
            column--;
        }
        line = i;
        column = j;
        while(line >= 0 && column < n) {
            String val = line + "," + column;
            coordinates.add(val);
            line--;
            column++;
        }
        line = i;
        column = j;
        while(line < n && column >=0) {
            String val = line + "," + column;
            coordinates.add(val);
            line++;
            column--;
        }
    }

    // 2.回溯 -- 剪枝
    // 不在同一列 + 不在两条斜线
    // 自顶向下 从左到右 ==> 行下标与列下标之差相等
    // 自顶向下 从右到左 ==> 行下标与列下标之和相等
    public List<List<String>> solveNQueens1(int n) {
        List<List<String>> res = new ArrayList<>();
        List<String> temp = new LinkedList<>();
        List<String> situation = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        for(int i =0;i<n;i++) {
            str.append(".");
        }
        for(int i =0;i<n;i++) {
            str.replace(i,i+1,"Q");
            situation.add(str.toString());
            str.replace(i,i+1,".");
        }
        nQueens2(n,res,temp,0,situation,new boolean[n],new HashSet<>(),new HashSet<>());
        return res;
    }

    private void nQueens2(int n,List<List<String>> res , List<String> temp ,int column,List<String> situation,
                          boolean[] lines,Set<Integer> diagonals1,Set<Integer> diagonals2) {
        if(column == n) {
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int line = 0 ; line < n;line++) {
            if(lines[line]) {
                continue;
            }
            if(diagonals1.contains(column - line) || diagonals2.contains(column + line)) {
                continue;
            }
            temp.add(situation.get(line));
            lines[line] = true;
            diagonals1.add(column-line);
            diagonals2.add(column+line);
            nQueens2(n,res,temp,column+1,situation,lines,diagonals1,diagonals2);
            // 回溯
            temp.remove(temp.size()-1);
            lines[line] = false;
            diagonals1.remove(column-line);
            diagonals2.remove(column+line);
        }
    }

    /*
    * #problem 102 二叉树的层序遍历
    * */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        if(root== null) {
            return res;
        }
        Deque<TreeNode> queue = new LinkedList();
        queue.addLast(root);
        while(!queue.isEmpty()) {
            int len = queue.size();
            List<Integer> temp = new ArrayList<>();
            for(int i =0;i<len;i++) {
                TreeNode cur = queue.removeFirst();
                temp.add(cur.val);
                if(cur.left != null) {
                    queue.addLast(cur.left);
                }
                if(cur.right != null) {
                    queue.addLast(cur.right);
                }
            }
            res.add(temp);
        }
        return res;
    }

    /*
    * #problem 433 最小基因变化
    * */
    // 1. BFS 将每一种可能加入到队列中 ==> 将每一层的所有可能性都加入到队列中
    public int minMutation(String startGene, String endGene, String[] bank) {
        char[] genes = new char[]{'A','C','G','T'};
        Set<String> banks = new HashSet<>();
        for(String t : bank) {
            banks.add(t);
        }
        if(startGene.equals(endGene)) {
            return 0;
        }
        if(!banks.contains(endGene)) {
            return -1;
        }
        // 记录已经使用过的基因序列
        Set<String> visited = new HashSet<>();
        Deque<String> queue = new LinkedList();
        queue.addLast(startGene);
        visited.add(startGene);
        int step = 0;
        while(!queue.isEmpty()) {
            int len = queue.size();
            // 取出所有的基因序列，进行基因变换操作
            for(int i =0;i<len;i++) {
                String curGene = queue.removeFirst();
                if(curGene.equals(endGene)) {
                    return step;
                }
                for(int j = 0;j<curGene.length();j++) {
                    // 对当前位置进行基因变换操作
                    for(int k = 0;k<genes.length;k++) {
                        if(curGene.charAt(j) == genes[k]) {
                            continue;
                        }
                        StringBuilder sb = new StringBuilder(curGene);
                        sb.setCharAt(j,genes[k]);
                        String newGene = sb.toString();
                        if(!visited.contains(newGene) && banks.contains(newGene)) {
                            // 当前基因序列符合条件
                            visited.add(newGene);
                            queue.addLast(newGene);
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

    // 2. DFS
    /*
    * 在基因组中找到与当前基因相差一个字符的基因，转换为该基因，然后进行DFS
    * 需要记录要转换的基因是否已经被转换过了 ==> 如果被转换过，就不进行转换
    * */
    private int min = Integer.MAX_VALUE;
    private Set<String> visited = new HashSet<>();
    public int minMutation1(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)) {
            return 0;
        }
        int i =0;
        for(;i<bank.length;i++) {
            if(endGene.equals(bank[i])) {
                break;
            }
        }
        if(i>= bank.length) {
            return -1;
        }
        visited.add(startGene);
        minMutationDFS(startGene,endGene,bank,0);
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private void minMutationDFS(String startGene,String endGene,String[] bank,int step) {
        if(startGene.equals(endGene)) {
            min = Math.min(min,step);
            return ;
        }
        char[] chars = startGene.toCharArray();
        for(String t : bank) {
            int diff = 0;
            for(int i =0;i<t.length();++i) {
                if(t.charAt(i) != chars[i]) {
                    diff++;
                }
            }
            if(diff == 1 && !visited.contains(t)) {
                // 进行基因变化
                visited.add(t);
                minMutationDFS(t,endGene,bank,step+1);
                // 回溯
                visited.remove(t);
            }
        }
    }

    @Test
    void test1(){
        System.out.println(minMutation2("AACCGGTT","AACCGGTA",new String[]{"AACCGGTA"}));
    }
    // 3. 双向BFS --> 避免搜索空间爆炸问题
    private char[] genes = new char[]{'A','C','G','T'};
    public int minMutation2(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)) {
            return 0;
        }
        Set<String> bankSet = Arrays.stream(bank).collect(Collectors.toSet());
        List<String> banks = new ArrayList<>(Arrays.asList(bank));
        banks.add(startGene);
        if(!bankSet.contains(endGene)) {
            return -1;
        }
        // q1 从startGene 开始搜索 q2从endGene开始搜索
        Deque<String> q1 = new LinkedList<>(),q2 = new LinkedList<>();
        // m1 记录 从 start基因变化为key基因需要几步
        // m2 记录 从 end基因变化为key基因需要几步
        Map<String,Integer> m1 = new HashMap<>(),m2 = new HashMap<>();
        q1.addLast(startGene);
        m1.put(startGene,0);
        q2.addLast(endGene);
        m2.put(endGene,0);
        // 某个为空，说明他们没有相遇==> 找不到结果
        while(!q1.isEmpty() && !q2.isEmpty()) {
            int res = -1;
            if(q1.size() < q2.size()) {
                res = updateQueue(q1,m1,m2,banks);
            } else {
                res = updateQueue(q2,m2,m1,banks);
            }
            if(res != -1) {
                return res;
            }
        }

        return -1;
    }

    private int updateQueue(Deque<String> queue,Map<String,Integer> cur,Map<String,Integer> other,List<String> bank) {
        int len = queue.size();
        for(int i=0;i<len;i++) {
            String curGene = queue.removeFirst();
            int step = cur.get(curGene);
            // 找到与当前基因相差一个字符的基因
            for(String t : bank) {
                int diff = 0;
                for(int j=0;j<t.length();j++) {
                    if(curGene.charAt(j) != t.charAt(j)) {
                        diff++;
                    }
                    if(diff > 1) {
                        break;
                    }
                }
                if(diff != 1) {
                    continue;
                }
                if(cur.containsKey(t) ) {
                    continue;
                }
                if(other.containsKey(t)) {
                    return step + 1 + other.get(t);
                }
                cur.put(t,step+1);
                queue.addLast(t);
            }
        }
        return -1;
    }

    /*
    * #problem 515 在每个树行中找最大值
    * */
    // 1. 层序遍历即可 （BFS)
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for(int i =0;i<size;i++) {
                TreeNode curNode = queue.poll();
                max = Math.max(max,curNode.val);
                if(curNode.left  != null ) {
                    queue.offer(curNode.left);
                }
                if(curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            res.add(max);
        }
        return res;
    }

    //2. DFS ==> 使用一个参数来记录当前层数，每走到一个节点时，就更新对应层的最大高度
    public List<Integer> largestValues2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        f(root,0,res);
        return res;
    }

    private void f(TreeNode root,int curH,List<Integer> res ) {
        if(curH == res.size()) {
            // 说明当前层是第一次进入
            res.add(root.val);
        } else {
            res.set(curH,Math.max(res.get(curH),root.val));
        }
        if(root.left != null) {
            f(root.left,curH+1,res);
        }
        if(root.right != null ) {
            f(root.right,curH+1,res);
        }
    }

    /*
    * #problem 127 单词接龙
    * 类似与 433 最小基因变化
    * */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) {
            return 1;
        }
        int i =0;
        while(i<wordList.size()) {
            if(wordList.get(i).equals(endWord)) {
                break;
            }
            i++;
        }
        if(i== wordList.size()) {
            return 0;
        }
        // 直接使用BFS
        Set<String> visited = new HashSet<>();
        Deque<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int step = 1;
        while(!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for(i =0;i<size;i++) {
                String curWord = queue.poll();
                for(String word : wordList) {
                    if(visited.contains(word)) {
                        continue;
                    }
                    // 只相差一个，可以进行转换
                    if(judgeDiffOne(curWord,word)) {
                        if(word.equals(endWord)) {
                            return step;
                        }
                        queue.offer(word);
                        visited.add(word);
                    }
                }
            }
        }
        return 0;
    }

    // 2. 双向BFS
    public int ladderLength2(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) {
            return 1;
        }
        if(!isExist(endWord,wordList)) {
            return 0;
        }
        Deque<String> q1 = new LinkedList<>(),q2 = new LinkedList<>();
        Map<String,Integer> m1 = new HashMap<>(),m2 = new HashMap<>();
        wordList.add(beginWord);
        q1.offer(beginWord);
        m1.put(beginWord,1);
        q2.offer(endWord);
        m2.put(endWord,1);
        while(!q1.isEmpty() && !q2.isEmpty()) {
            int res = -1;
            if(q1.size() <= q2.size()) {
                res = updateQ(q1,m1,m2,wordList);
            } else {
                res = updateQ(q2,m2,m1,wordList);
            }
            if(res != -1) {
                return res;
            }
        }

        return 0;

    }
    private int updateQ(Queue<String> queue,Map<String,Integer> cur,Map<String,Integer> other,
                        List<String> wordList) {
        int size = queue.size();
        for(int i =0;i<size;i++) {
            String curWord = queue.poll();
            int step = cur.get(curWord);
            for(String t : wordList) {
                if(cur.containsKey(t)) {
                    continue;
                }
                if(judgeDiffOne(curWord,t)) {
                    if(other.containsKey(t)) {
                        return step + 1 + other.get(t);
                    }
                    queue.offer(t);
                    visited.add(t);
                    cur.put(t,step+1);
                }
            }
        }
        return -1;
    }

    // 3. DFS
    private int ladderLengthMin = Integer.MAX_VALUE;
    public int ladderLength3(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) {
            return 1;
        }
        if(!isExist(endWord,wordList)) {
            return 0;
        }
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        ladderLengthF(beginWord,endWord,visited,wordList,0);
        return ladderLengthMin == Integer.MAX_VALUE ? 0 : ladderLengthMin;
    }

    private void ladderLengthF(String beginWord,String endWord,Set<String> visited,List<String> wordList,int step) {
        if(beginWord.equals(endWord)) {
            ladderLengthMin = Math.min(ladderLengthMin,step);
            return ;
        }
        for(String word : wordList) {
            if(!visited.contains(word) && judgeDiffOne(word, beginWord)) {
                visited.add(word);
                ladderLengthF(word,endWord,visited,wordList,step+1);
                visited.remove(word);
            }
        }
    }

    /*
    * #problem 126 单词接龙II
    * */
    @Test
    void test3(){
        findLadders2("hit",
                "cog",
                Arrays.asList("hot","dot","dog","lot","log","cog"));
    }
    // 1. 得到所有的最短序列 ==> BFS ，最先达到要求的就是最短的转换序列（相同层，达到要求的，都是最短的转换序列）
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        if(beginWord.equals(endWord)) {
            List<String> temp = new ArrayList<>(Collections.singletonList(beginWord));
            res.add(temp);
            return res;
        }
        Set<String> wordSet = new HashSet<>(wordList);
        if(!wordSet.contains(endWord)) {
            return res;
        }
        wordSet.add(beginWord);
        Deque<String> q1 =new LinkedList<>(),q2 = new LinkedList<>();
        Map<String,List<List<String>>> m1 = new HashMap<>(), m2 = new HashMap<>();
        q1.offer(beginWord);
        m1.put(beginWord,new ArrayList<>(Collections.singletonList(new ArrayList<>(Collections.singletonList(beginWord)))));
        q2.offer(endWord);
        m2.put(endWord,new ArrayList<>(Collections.singletonList(new ArrayList<>(Collections.singletonList(endWord)))));
        while(!q1.isEmpty() && !q2.isEmpty()) {
            boolean flag = false;
            if(q1.size() <= q2.size()) {
                flag = updateQ2(q1,m1,m2,wordSet,true,res);
            } else {
                flag = updateQ2(q2,m2,m1,wordSet,false,res);
            }
            if(flag) {
                return res;
            }
        }

        return res;
    }

    private boolean updateQ2(Deque<String> queue,Map<String,List<List<String>>> cur,Map<String,List<List<String>>> other,
                             Set<String> wordSet,boolean isForward,List<List<String>> res) {
        int size = queue.size();
        boolean flag = false;
        // 所以某个 nextWord可能会被多次使用，因此先存储关系，最后再添加
        Map<String,List<List<String>>> subCur = new HashMap<>();
        for(int i =0;i<size;i++) {
            String curWord = queue.poll();
            // 到达当前当前的路径可能有多条
            List<List<String>> paths = cur.get(curWord);
            for(String nextWord : wordSet) {
                // 已经使用过
                if(cur.containsKey(nextWord) || !judgeDiffOne(nextWord,curWord)) {
                    continue;
                }
                // 找到
                List<List<String>> nextPaths = subCur.getOrDefault(nextWord,new ArrayList<>());
                if(other.containsKey(nextWord)) {
                    flag = true;
                    res.addAll(buildPath(paths,other.get(nextWord),isForward));
                } else {
                    // 还未到达终点
                    nextPaths.addAll(buildPath(paths, nextWord));
                    subCur.put(nextWord,nextPaths);
                }
            }
        }
        cur.putAll(subCur);
        queue.addAll(subCur.keySet());
        return flag;
    }

    private List<List<String>> buildPath(List<List<String>> paths,String nextWords) {
        List<List<String>> res = new ArrayList<>();
        for(List<String> path : paths) {
            List<String> newList = new ArrayList<>(path);
            newList.add(nextWords);
            res.add(newList);
        }
        return res;
    }

    private List<List<String>> buildPath(List<List<String>> paths,List<List<String>> paths2,boolean isForward) {
        List<List<String>> res = new ArrayList<>();
        List<List<String>> paths1 = paths;
        if(!isForward) {
            paths = paths2;
            paths2 = paths1;
        }
        for(List<String> path : paths) {
            for(List<String> path2 : paths2) {
                List<String> newList = new ArrayList<>(path);
                for(int i = path2.size()-1;i>=0;i--) {
                    newList.add(path2.get(i));
                }
                res.add(newList);
            }
        }
        return res;
    }

    // 2. BFS构建无向图 DFS搜索无向图
    public List<List<String>> findLadders2(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordList);
        if(!dict.contains(endWord)) {
            return res;
        }
        Deque<String> queue = new LinkedList<>();
        // 记录每个单词的最短步骤
        Map<String,Integer> steps = new HashMap<>();
        queue.offer(beginWord);
        steps.put(beginWord,0);
        dict.remove(beginWord);
        // 记录所有可以到 key 的 单词
        Map<String,List<String>> from = new HashMap<>();
        int step = 0;
        boolean found = false;
        while(!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for(int i =0;i<size;i++) {
                String curWord = queue.poll();
                char[] charArray = curWord.toCharArray();
                for(int j =0;j < charArray.length;j++) {
                    char origin = charArray[j];
                    for(char c = 'a'; c <= 'z';c++) {
                        charArray[j] = c;
                        String nextWord = String.valueOf(charArray);
                        if(steps.containsKey(nextWord) && step == steps.get(nextWord)) {
                            // 说明nextWord 之前有到达过
                            from.get(nextWord).add(curWord);
                        }
                        if(!dict.contains(nextWord)) {
                            // 判断当前单词是否存在/遍历过
                            continue;
                        }
                        // 防止该单词被重复生成
                        dict.remove(nextWord);
                        steps.put(nextWord,step);
                        from.putIfAbsent(nextWord,new ArrayList<>());
                        from.get(nextWord).add(curWord);
                        queue.offer(nextWord);
                        if(nextWord.equals(endWord)) {
                            found = true;
                        }
                    }
                    charArray[j] = origin;
                }
            }
            if(found) {
                break;
            }
        }
        // 进行DFS搜索
        if(found) {
            Deque<String> path = new LinkedList<>();
            path.add(endWord);
            dfs(from,path,res,beginWord,endWord);
        }
        return res;
    }

    private void dfs(Map<String,List<String>> from , Deque<String> path,List<List<String>> res,String beginWord,String endWord) {
        if(endWord.equals(beginWord)) {
            res.add(new ArrayList<>(path));
            return ;
        }
        for(String word : from.get(endWord)) {
            path.addFirst(word);
            dfs(from,path,res,beginWord,word);
            path.removeFirst();
        }
    }





    private boolean isExist(String word ,List<String> wordList) {
        return wordList.stream().anyMatch(word::equals);
    }

    private boolean judgeDiffOne(String s1,String s2) {
        int diff = 0;
        for(int i =0;i<s1.length() && diff <= 1;i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }

    /*
    * #problem 200. 岛屿数量
    * */
    // 1. dfs
    public int numIslands(char[][] grid) {
        int res = 0;
        boolean[][] visited = new boolean[grid[0].length][grid.length];
        for(int column = 0;column < grid[0].length;column ++ ) {
            for(int line = 0; line < grid.length;line ++) {
                if(grid[column][line] == '1' && !visited[column][line]) {
                    res++;
                    dfsLand(grid,column,line,visited);
                }
            }
        }
        return res;
    }

    private void dfsLand(char[][] grid,int column,int line,boolean[][] visited) {
        if(column < 0 || column >= grid.length || line < 0 || line >= grid[0].length) {
            return ;
        }

        if(visited[column][line] || grid[column][line] == '0') {
            return ;
        }
        visited[column][line] = true;
        // 上下左右搜索
        dfsLand(grid,column-1,line,visited);
        dfsLand(grid,column+1,line,visited);
        dfsLand(grid,column,line+1,visited);
        dfsLand(grid,column,line-1,visited);
    }

    // 2. BFS ==> 将深搜搜索到的位置改为0
    public int numIslands2(char[][] grid) {
        int columnLen = grid.length;
        int lineLen = grid[0].length;
        int res = 0;
        for(int i =0;i<columnLen;i++) {
            for(int j =0;j<lineLen;j++) {
                if(grid[i][j] == '1') {
                    res ++ ;
                    grid[i][j] = '0';
                    Deque<Integer> queue = new LinkedList<>();
                    queue.offer(i * lineLen + j);
                    while(!queue.isEmpty()) {
                        int size = queue.size();
                        for(int k = 0;k<size;k++) {
                            int id = queue.poll();
                            int row = id/lineLen;
                            int l = id % lineLen;
                            // 上
                            if(row -1 >= 0 && grid[row-1][l] == '1') {
                                grid[row-1][l] = '0';
                                queue.add((row-1) * lineLen + l);
                            }
                            if(row + 1 < columnLen && grid[row+1][l] == '1') {
                                grid[row+1][l] = '0';
                                queue.add((row+1) * lineLen + l);
                            }
                            // 左
                            if(l -1 >= 0 && grid[row][l-1] == '1') {
                                grid[row][l-1] = '0';
                                queue.add(row * lineLen + l -1);
                            }
                            if( l + 1 < lineLen && grid[row][l +1] == '1') {
                                grid[row][l+1] = '0';
                                queue.add(row * lineLen + l + 1);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }


    /*
    * #problem 529 扫雷游戏
    * */
    public char[][] updateBoard(char[][] board, int[] click) {
        int row = click[0];
        int col = click[1];
        if(board[row][col] == 'M') {
            board[row][col] = 'M';
            return board;
        }

        int rowLen = board.length;
        int colLen = board[0].length;
        int[][] visited = new int[rowLen][colLen];
        dfs(board,row,col,visited);
        return board;
    }

    private void dfs(char[][] board,int row,int col,int[][] visited) {
        if(row < 0 || row >= board.length || col < 0 || col >= board[0].length  || visited[row][col] == 1) {
            return ;
        }
        visited[row][col] = 1;
        if(board[row][col] == 'M') {
            return ;
        }
        // 空方块
        if(board[row][col] == 'E') {
            board[row][col] = 'B';
            // 判断上下左右 + 两条斜线 是否有地雷，有的话
            // 上
            int num = 0;
            if(row -1 >=0 && board[row-1][col] == 'M') {
                num ++;
            }
            // 下
            if(row +1 < board.length && board[row+1][col] == 'M') {
                num ++;
            }
            // 左
            if(col -1 >= 0 && board[row][col-1] == 'M') {
                num ++;
            }
            // 右
            if(col +1 < board[0].length && board[row][col +1] == 'M') {
                num ++;
            }
            // 斜线
            if(row -1 >= 0 && col -1 >=0 && board[row-1][col-1] == 'M') {
                num++;
            }
            if(row+1 < board.length && col +1 < board[0].length && board[row+1][col+1] == 'M') {
                num++;
            }
            if(row +1 < board.length && col -1 >=0 && board[row+1][col-1] == 'M') {
                num++;
            }
            if(row-1 >=0 && col+1 < board[0].length && board[row-1][col+1] == 'M') {
                num++;
            }
            if(num != 0) {
                board[row][col] = (char)('0' + num);
            } else {
                // 递归 (需要向八个方向遍历）
                dfs(board,row+1,col,visited);
                dfs(board,row-1,col,visited);
                dfs(board,row,col+1,visited);
                dfs(board,row,col-1,visited);
                dfs(board,row-1,col-1,visited);
                dfs(board,row+1,col+1,visited);
                dfs(board,row+1,col-1,visited);
                dfs(board,row-1,col+1,visited);
            }
        }

    }
    // 2. bfs 将B的八个方向的地址加入（八个方向需要不是地雷）
    public char[][] updateBoard2(char[][] board, int[] click) {
        int[] rows = new int[]{-1,1,0,0,-1,1,1,-1};
        int[] cols = new int[]{0,0,-1,1,-1,1,-1,1};
        int rowLen = board.length;
        int colLen = board[0].length;
        int row = click[0];
        int col = click[1];
        if(board[row][col] == 'M') {
            board[row][col] = 'X';
        } else {
          Deque<int[]> queue = new LinkedList<>();
          int[][] visited = new int[rowLen][colLen];
          visited[row][col] = 1;
          queue.offer(new int[]{row,col});
          while(!queue.isEmpty()) {
              int[] poll = queue.poll();
              int x =poll[0];
              int y =poll[1];
              int count = 0;

              // 判断当前位置的8个方向是否有地雷
              for(int l = 0;l<8;l++) {
                  int tx = x + rows[l];
                  int ty = y + cols[l];
                  if( tx < 0 || tx >= rowLen || ty < 0 || ty >= colLen) {
                      continue;
                  }
                  if(board[tx][ty] == 'M') {
                      count ++;
                  }
              }
              if(count > 0) {
                  // 有地雷
                  board[x][y] = (char)('0' + count);
              } else {
                  board[x][y] = 'B';
                  // 将当前位置的8个方向的符合条件的地址加入到队列种
                  for(int l = 0;l<8;l++) {
                      int tx = x + rows[l];
                      int ty = y + cols[l];
                      if( tx < 0 || tx >= rowLen || ty < 0 || ty >= colLen || visited[tx][ty] == 1 || board[tx][ty] != 'E') {
                          continue;
                      }
                      queue.offer(new int[]{tx,ty});
                      visited[tx][ty] = 1;
                  }
              }

          }
        }

        return board;
    }




}
